<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
<meta name="viewport"
      content="width=device-width, initial-scale=1.0, maximum-scale=1.0, minimum-scale=1.0">
<meta http-equiv="X-UA-Compatible" content="ie=edge">

    <meta name="author" content="Mouweng">





<title>B树与B+树 | Mouweng&#39;s Blog</title>



    <link rel="icon" href="/favicon.ico">




    <!-- stylesheets list from _config.yml -->
    
    <link rel="stylesheet" href="/css/style.css">
    



    <!-- scripts list from _config.yml -->
    
    <script src="/js/script.js"></script>
    
    <script src="/js/tocbot.min.js"></script>
    



    
    
        
    


<meta name="generator" content="Hexo 5.1.1"><link rel="alternate" href="/atom.xml" title="Mouweng's Blog" type="application/atom+xml">
</head>
<body>
    <div class="wrapper">
        <header>
    <nav class="navbar">
        <div class="container">
            <div class="navbar-header header-logo"><a href="/">Mouweng</a></div>
            <div class="menu navbar-right">
                
                    <a class="menu-item" href="/archives">Posts</a>
                
                    <a class="menu-item" href="/category">Categories</a>
                
                    <a class="menu-item" href="/tag">Tags</a>
                
                    <a class="menu-item" href="/about">About</a>
                
                <input id="switch_default" type="checkbox" class="switch_default">
                <label for="switch_default" class="toggleBtn"></label>
            </div>
        </div>
    </nav>

    
    <nav class="navbar-mobile" id="nav-mobile">
        <div class="container">
            <div class="navbar-header">
                <div>
                    <a href="/">Mouweng</a><a id="mobile-toggle-theme">·&nbsp;Light</a>
                </div>
                <div class="menu-toggle" onclick="mobileBtn()">&#9776; Menu</div>
            </div>
            <div class="menu" id="mobile-menu">
                
                    <a class="menu-item" href="/archives">Posts</a>
                
                    <a class="menu-item" href="/category">Categories</a>
                
                    <a class="menu-item" href="/tag">Tags</a>
                
                    <a class="menu-item" href="/about">About</a>
                
            </div>
        </div>
    </nav>

</header>
<script>
    var mobileBtn = function f() {
        var toggleMenu = document.getElementsByClassName("menu-toggle")[0];
        var mobileMenu = document.getElementById("mobile-menu");
        if(toggleMenu.classList.contains("active")){
           toggleMenu.classList.remove("active")
            mobileMenu.classList.remove("active")
        }else{
            toggleMenu.classList.add("active")
            mobileMenu.classList.add("active")
        }
    }
</script>
        <div class="main">
            <div class="container">
    
    
        <div class="post-toc">
    <div class="tocbot-list">
    </div>
    <div class="tocbot-list-menu">
        <a class="tocbot-toc-expand" onclick="expand_toc()">Expand all</a>
        <a onclick="go_top()">Back to top</a>
        <a onclick="go_bottom()">Go to bottom</a>
    </div>
</div>

<script>
    document.ready(
        function () {
            tocbot.init({
                tocSelector: '.tocbot-list',
                contentSelector: '.post-content',
                headingSelector: 'h1, h2, h3, h4, h5',
                collapseDepth: 1,
                orderedList: false,
                scrollSmooth: true,
            })
        }
    )

    function expand_toc() {
        var b = document.querySelector(".tocbot-toc-expand");
        tocbot.init({
            tocSelector: '.tocbot-list',
            contentSelector: '.post-content',
            headingSelector: 'h1, h2, h3, h4, h5',
            collapseDepth: 6,
            orderedList: false,
            scrollSmooth: true,
        });
        b.setAttribute("onclick", "collapse_toc()");
        b.innerHTML = "Collapse all"
    }

    function collapse_toc() {
        var b = document.querySelector(".tocbot-toc-expand");
        tocbot.init({
            tocSelector: '.tocbot-list',
            contentSelector: '.post-content',
            headingSelector: 'h1, h2, h3, h4, h5',
            collapseDepth: 1,
            orderedList: false,
            scrollSmooth: true,
        });
        b.setAttribute("onclick", "expand_toc()");
        b.innerHTML = "Expand all"
    }

    function go_top() {
        window.scrollTo(0, 0);
    }

    function go_bottom() {
        window.scrollTo(0, document.body.scrollHeight);
    }

</script>
    

    
    <article class="post-wrap">
        <header class="post-header">
            <h1 class="post-title">B树与B+树</h1>
            
                <div class="post-meta">
                    
                        Author: <a itemprop="author" rel="author" href="/">Mouweng</a>
                    

                    
                        <span class="post-time">
                        Date: <a href="#">August 26, 2020&nbsp;&nbsp;23:41:12</a>
                        </span>
                    
                    
                        <span class="post-category">
                    Category:
                            
                                <a href="/categories/mysql/">mysql</a>
                            
                        </span>
                    
                </div>
            
        </header>

        <div class="post-content">
            <p><a target="_blank" rel="noopener" href="https://www.cs.usfca.edu/~galles/visualization/BTree.html">B tree演示动画</a></p>
<p><a target="_blank" rel="noopener" href="https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html">B+ tree演示动画</a></p>
<h2 id="背景"><a href="#背景" class="headerlink" title="背景"></a>背景</h2><p>动态查找树主要包括：二叉搜索树，平衡二叉树，红黑树，B树</p>
<p>B树时间复杂度O(log2N)，通过对树高度的降低可以提升查找效率，尤其是在大量数据进行存储时会存储到外部磁盘，通过对外部磁盘的读取需要快速查找到对应位置，所以需要一种高效的外存数据结构。</p>
<p><strong>B树&amp;B+树：就是为了存储设备或磁盘而设计的一种所有结点平衡因子均等于0的多路查找树</strong></p>
<h2 id="B树"><a href="#B树" class="headerlink" title="B树"></a>B树</h2><h4 id="定义"><a href="#定义" class="headerlink" title="定义"></a>定义</h4><blockquote>
<p>对于一棵m阶的B树</p>
<p>1）树中的每个节点最多有m个孩子 </p>
<p>2）除了根节点和叶子节点外，其他节点最少含有m/2（取上限）个孩子 </p>
<p>3）若根节点不是叶子节点，则根节点最少含有两个孩子 </p>
<p>4）所以叶子节点都在同一层，且叶子结点为NULL</p>
</blockquote>
<h4 id="查找"><a href="#查找" class="headerlink" title="查找"></a>查找</h4><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">和二叉查找树过程类似，只是为多叉查找。</span><br><span class="line">比较的次数并不比二叉查找树少，尤其适当某一节点中的数据很多时，但是磁盘IO的次数却是大大减少。比较是在内存中进行的（即在找到目标节点后，先将结点中的信息读入内存），相比于磁盘IO的速度，比较的耗时几乎可以忽略。所以当树的高度足够低的话，就可以极大的提高效率。</span><br></pre></td></tr></table></figure>

<h4 id="插入"><a href="#插入" class="headerlink" title="插入"></a>插入</h4><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line">对于高度为h的m阶B树，新节点一般插在第h层。	</span><br><span class="line">1）若该节点中关键码个数小于m-1，则直接插入</span><br><span class="line">2）若该节点中关键码个数等于m-1，则节点分裂。以中间的关键码为界，</span><br><span class="line">	 将节点一分为二，产生一个新的节点，并将中间关键码插入到父节点中。</span><br><span class="line">重复上述过程，最坏情况一直分裂高根节点，则B树就会增加一层。</span><br></pre></td></tr></table></figure>

<h4 id="删除"><a href="#删除" class="headerlink" title="删除"></a>删除</h4><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line">情况一：删除的关键字K不在终端结点</span><br><span class="line">（1）从k的前驱选取最大或者后继子树中选取最小来替代K即可，只要满足前驱或后继关键字个数大于m&#x2F;2(向上取整)-1.</span><br><span class="line">（2）如果前驱和后继均不满足，直接将前驱和后继合并，然后删除K.</span><br><span class="line">情况二：删除的关键字在终端结点（第h层）</span><br><span class="line">（1）自己够删，关键字所在结点关键字个数足够（关键字大于m&#x2F;2(向上取整)-1），关键字直接删除</span><br><span class="line">（2）兄弟够借，兄弟关键字所在结点关键字个数足够（关键字大于m&#x2F;2(向上取整)-1），关键字删除，借父亲一位，兄弟顶父亲。</span><br><span class="line">（3）兄弟不够借，把关键字删除，自己、兄弟、以及父亲那一位关键字合并。</span><br></pre></td></tr></table></figure>





<h2 id="B-树"><a href="#B-树" class="headerlink" title="B+树"></a>B+树</h2><p>Ｂ＋树是Ｂ树的变种，有着比Ｂ树更高的查询效率。</p>
<h4 id="定义-1"><a href="#定义-1" class="headerlink" title="定义"></a>定义</h4><blockquote>
<p>1）有k个子树的中间节点包含有k个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引。</p>
<p>2）所有分支结点中仅包含各个子节点中关键字最大的值和指向其子节点的指针。 </p>
<p>3）所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字自小而大顺序链接。</p>
<p>4）B+树通常有两个指针，一个指向根结点，另一个指向关键字最小的叶子结点。因些，对于B+树进行查找两种运算：一种是从最小关键字起顺序查找，另一种是从根结点开始，进行随机查找。</p>
</blockquote>
<h4 id="插入-1"><a href="#插入-1" class="headerlink" title="插入"></a>插入</h4><p>B+树的插入与B树的插入过程类似。不同的是B+树在叶结点上进行，如果叶结点中的关键码个数超过m，就必须分裂成关键码数目大致相同的两个结点，并保证上层结点中有这两个结点的最大关键码。</p>
<h4 id="删除-1"><a href="#删除-1" class="headerlink" title="删除"></a>删除</h4><p>B+树中的关键码在叶结点层删除后，其在上层的复本可以保留，作为一个”分解关键码”存在，如果因为删除而造成结点中关键码数小于ceil(m/2)，其处理过程与B树的处理一样。</p>
<h2 id="总结"><a href="#总结" class="headerlink" title="总结"></a>总结</h2><h4 id="B-树相比B树的优势："><a href="#B-树相比B树的优势：" class="headerlink" title="B+树相比B树的优势："></a>B+树相比B树的优势：</h4><ol>
<li>单一节点存储更多的元素，使得查询的IO次数更少； </li>
<li>所有查询都要查找到叶子节点，查询性能稳定； </li>
<li>所有叶子节点形成有序链表，便于范围查询。</li>
</ol>
<h4 id="具体分析"><a href="#具体分析" class="headerlink" title="具体分析"></a>具体分析</h4><p>（1）Ｂ＋树中间节点没有卫星数据（索引元素所指向的数据记录），只有索引。而Ｂ树每个结点中的每个关键字都有卫星数据；这就意味着同样的大小的磁盘页可以容纳更多节点元素，在相同的数据量下，Ｂ＋树更加“矮胖”，Ｉ/Ｏ操作更少 。</p>
<ul>
<li>B树的卫星数据 </li>
</ul>
<p><img src="https://tva1.sinaimg.cn/large/006tNbRwgy1g9kzd2h1s8j30hs08mq33.jpg"></p>
<ul>
<li>B+树的卫星数据</li>
</ul>
<p><img src="https://tva1.sinaimg.cn/large/006tNbRwgy1g9kzdb6uawj30hs085glq.jpg"></p>
<p>（2）Ｂ树的查找只需找到匹配元素即可，最好情况下查找到根节点，最坏情况下查找到叶子结点，所说性能很不稳定，而Ｂ＋树每次必须查找到叶子结点，性能稳定 </p>
<p>（3）在范围查询方面，B+树的优势更加明显<br>　　B树的范围查找需要不断依赖中序遍历。首先二分查找到范围下限，在不断通过中序遍历，知道查找到范围的上限即可。整个过程比较耗时。<br>　　而B+树的范围查找则简单了许多。首先通过二分查找，找到范围下限，然后同过叶子结点的链表顺序遍历，直至找到上限即可，整个过程简单许多，效率也比较高。 </p>
<p>​        例如：同样查找范围[3-11]，两者的查询过程如下： </p>
<ul>
<li>B树的查找过程</li>
</ul>
<p><img src="https://tva1.sinaimg.cn/large/006tNbRwgy1g9kzgov58aj30fo0g0406.jpg"></p>
<ul>
<li>B+树的查找过程</li>
</ul>
<p><img src="https://tva1.sinaimg.cn/large/006tNbRwgy1g9kzhlqaftj30pq0iw786.jpg"></p>

        </div>

        
            <section class="post-copyright">
                
                
                
                

            </section>
        
        <section class="post-tags">
            <div>
                <span>Tag(s):</span>
                <span class="tag">
                    
                    
                        <a href="/tags/B%E6%A0%91/"># B树</a>
                    
                        <a href="/tags/B-%E6%A0%91/"># B+树</a>
                    
                        
                </span>
            </div>
            <div>
                <a href="javascript:window.history.back();">back</a>
                <span>· </span>
                <a href="/">home</a>
            </div>
        </section>
        <section class="post-nav">
            
                <a class="prev" rel="prev" href="/2020/08/26/git/">Git版本控制工具</a>
            
            
            <a class="next" rel="next" href="/2020/08/26/%E6%B5%B7%E9%87%8F%E6%95%B0%E6%8D%AE%E5%A4%84%E7%90%86%E9%9D%A2%E8%AF%95%E9%A2%98%E8%A7%A3%E7%AD%94%E6%A8%A1%E6%9D%BF/">海量数据处理面试题</a>
            
        </section>


    </article>
</div>

        </div>
        <footer id="footer" class="footer">
    <div class="copyright">
        <span>© Mouweng | Powered by <a href="https://hexo.io" target="_blank">Hexo</a> & <a href="https://github.com/Siricee/hexo-theme-Chic" target="_blank">Chic</a></span>
    </div>
</footer>

    </div>
</body>
</html>
